|
In set theory, Cantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument or the diagonal method, was published in 1891 by Georg Cantor as a mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural numbers.〔 (in german)〕 Such sets are now known as uncountable sets, and the size of infinite sets is now treated by the theory of cardinal numbers which Cantor began. The diagonal argument was not Cantor's first proof of the uncountability of the real numbers; it was actually published much later than his first proof, which appeared in 1874. However, it demonstrates a powerful and general technique that has since been used in a wide range of proofs, also known as diagonal arguments by analogy with the argument used in this proof. The most famous examples are perhaps Russell's paradox, the first of Gödel's incompleteness theorems, and Turing's answer to the ''Entscheidungsproblem''. Historically, the diagonal argument first appeared in the work of Paul du Bois-Reymond in 1875. == Uncountable set == In his 1891 article, Cantor considered the set ''T'' of all infinite sequences of binary digits (i.e. consisting only of zeroes and ones). He begins with a constructive proof of the following theorem: :If ''s''1, ''s''2, … , ''s''''n'', … is any enumeration of elements from ''T'', then there is always an element ''s'' of ''T'' which corresponds to no ''s''''n'' in the enumeration. To prove this, given an enumeration of arbitrary members from ''T'', like e.g. : he constructs the sequence ''s'' by choosing its ''n''th digit as complementary to the ''n''th digit of ''s''''n'', for every ''n''. In the example, this yields: : By construction, ''s'' differs from each ''s''''n'', since their ''n''th digits differ (highlighted in the example). Hence, ''s'' cannot occur in the enumeration. Based on this theorem, Cantor then uses an indirect argument to show that: :The set ''T'' is uncountable. He assumes for contradiction that ''T'' was countable. Then (all) its elements could be written as an enumeration ''s''1, ''s''2, … , ''s''''n'', … . Applying the previous theorem to this enumeration would produce a sequence ''s'' not belonging to the enumeration. However, ''s'' was an element of ''T'' and should therefore be in the enumeration. This contradicts the original assumption, so ''T'' must be uncountable. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Cantor's diagonal argument」の詳細全文を読む スポンサード リンク
|